/************************************************************************************************
 * test examples of 100 interesting program in C
 * test 031.c
 * Goldbach's Conjecture
 ***********************************************************************************************/

#include <stdio.h>
#include <math.h>
#include <string.h>

/*
 *
 */

#define MAX 2000

int a[MAX/sizeof(int)+1];
int p[MAX];

int isPrime(int n)
{
	if (n < 2)
		return(0);
	else if (n == 2)
		return(1);
	else if (n % 2 == 0)
		return(0);
	int i = 0;
	int cut_off = sqrt(n);
	for (i = 0; i <= cut_off && p[i] != 0; i++)
		if (n % p[i] == 0) return(0);
	return(1);
}

int isSmallPrime(int n)
{
	int byte = (n-1) / (sizeof(int)*8);
	int bit = (n-1) % (sizeof(int)*8);

	// pay attention to this bit operation, "&"'s priority is so low...
	if (((1 << bit) & a[byte]) != 0)
		return(1);
	else
		return(0);
}

int main()
{
	memset(a, 0, sizeof(int)*(MAX/sizeof(int)+1));
	memset(p, 0, sizeof(int)*MAX);
	int i = 0, curr = 0;
	for (i = 1; i <= MAX; i++)
	{
		if (isPrime(i) == 1)
		{
			p[curr++] = i;
			int byte = (i-1) / (sizeof(int)*8);
			int bit = (i-1) % (sizeof(int)*8);
			a[byte] |= (1 << bit);
		}
		else if (i > 2 && i % 2 == 0)
		{
			int j = 0, flag = 0;
			for (j = 0; p[j] <= i/2; j++)
			{
				// printf("Testing %d = %d + %d\n", i, p[j], i-p[j]);
				if (isSmallPrime(i-p[j]) == 1)
				{
					printf("%d = %d + %d\n", i, p[j], i-p[j]);
					flag = 1;
					break;
				}
			}
			// counter-example
			if (flag == 0)
				printf("%d is a counter example of Goldbach's Conjecture\n");
		}
	}
}

